﻿using System;
using System.Collections.Generic;

namespace theeg.GeometryWpf
{
    /// <summary>
    /// This is the pseudo priority tree variant of the Hilbert Rectangle tree.
    /// It is derived from the Kd-Tree, where dimension is 2 and each node has
    /// up to two child nodes (left and right, like in a binary tree).
    /// It stores 4 nodes for each bounding rectangle of contained objects.
    /// - top left
    /// - top right
    /// - bottom left
    /// - bottom right
    /// If any of the areas controlled by these points lie in a requested area
    /// the object is considered to be invisible inside the requested area 
    /// (RangeSearch).
    /// 
    /// The hilbert curve is not of interest in this variant.
    /// </summary>
    public class HilbertTree
    {
        internal static int Dimensions = 2;
        Node _rootNode;

        public Node GetRoot()
        {
            return _rootNode;
        }

        public ComputationalRectangle GetSize()
        {
            if (_rootNode != null)
            {
                return _rootNode.BoundingRegion;
            }
            return new ComputationalRectangle();
        }

        Node Delete(IHilbertTreeNode data, Node t, int cd, bool bfound, Node.LowAndHighCombination lowAndHigh)
        {
            /*
             * search nodes downwards until the four nodes storing the TreeNodeData are found
             * if so, remove the node, traverse children, recalculate represented region
             * 
             */
            if (t == null) return null;
            if (data == t.StoredData)
            {
                if (t.Right != null)
                { // take replacement from right
                    t.StoredData = FindMinimum(t.Right, cd, (cd + 1) % Dimensions).StoredData;
                    t.Right = Delete(t.StoredData, t.Right, (cd + 1) % Dimensions, true, lowAndHigh);
                    if (!bfound)
                        t.RecalculateRegion();
                }
                else if (t.Left != null)
                { // take replacement from left
                    t.StoredData = FindMinimum(t.Left, cd, (cd + 1) % Dimensions).StoredData;
                    t.Right = Delete(t.StoredData, t.Left, (cd + 1) % Dimensions, true, lowAndHigh);
                    t.Left = null;
                    if (!bfound)
                        t.RecalculateRegion();
                }
                else
                    return null; // delete this leaf
            }
            else
            {
                double value1, value2;
                if (cd == 0)//X
                {
                    value2 = t.RepresentingPoint.X;
                    if (lowAndHigh == Node.LowAndHighCombination.LowXLowY ||
                        lowAndHigh == Node.LowAndHighCombination.LowXHighY)
                    {
                        //left
                        value1 = data.GetBoundingBox().L;
                    }
                    else
                    {
                        //right
                        value1 = data.GetBoundingBox().R;
                    }
                }
                else//Y
                {
                    value2 = t.RepresentingPoint.Y;
                    if (lowAndHigh == Node.LowAndHighCombination.LowXLowY ||
                        lowAndHigh == Node.LowAndHighCombination.HighXLowY)
                    {
                        //top
                        value1 = data.GetBoundingBox().T;
                    }
                    else
                    {
                        //bottom
                        value1 = data.GetBoundingBox().B;
                    }
                }
                if (value1 <= value2)
                {
                    t.Left = Delete(data, t.Left, (cd + 1) % Dimensions, bfound, lowAndHigh);
                }
                else
                {
                    t.Right = Delete(data, t.Right, (cd + 1) % Dimensions, bfound, lowAndHigh);
                }
            }
            return t;
        }

        Node FindMinimum(Node t, int i, int currentDimension)
        {
            if (t == null) return null;
            if (currentDimension == i)
            {
                // i == splitting axis
                if (t.Left == null) return t; // no left child?
                return FindMinimum(t.Left, i, (currentDimension + 1) % Dimensions);
            }
            // else min of both children and t
            return Minimum(t,
                           FindMinimum(t.Left, i, (currentDimension + 1) % Dimensions),
                           FindMinimum(t.Right, i, (currentDimension + 1) % Dimensions), i);
        }

        /// <summary>
        /// Get the minimum of two tree node data objects with respect to the coordinate
        /// in the given dimension.
        /// </summary>
        /// <param name="p1"></param>
        /// <param name="p2"></param>
        /// <param name="dimension"></param>
        /// <returns></returns>
        private Node Minimum(Node p1, Node p2, int dimension)
        {
            Node min = null;
            System.Windows.Point pt1 = p1.RepresentingPoint;
            System.Windows.Point pt2 = p2.RepresentingPoint;
            switch (dimension)
            {
                case 0://X
                    min = (pt1.X < pt2.X) ? p1 : p2;
                    break;
                case 1://Y
                    min = (pt1.Y < pt2.Y) ? p1 : p2;
                    break;
            }
            return min;
        }

        /// <summary>
        /// get the tree node out of 3 with smallest coordinate in given dimension
        /// </summary>
        /// <param name="p1">first node, must not be null</param>
        /// <param name="p2">second node</param>
        /// <param name="p3">third node</param>
        /// <param name="dimension">the dimension to check</param>
        /// <returns>the minimum out of 3 nodes</returns>
        private Node Minimum(Node p1, Node p2, Node p3, int dimension)
        {
            if (p1 == null) return null;
            Node min;
            if (p2 == null)
            {
                if (p3 == null)
                {
                    min = p1;
                }
                else
                {
                    min = Minimum(p1, p3, dimension);
                }
            }
            else
            {
                if (p3 == null)
                {
                    min = p2;
                }
                else
                {
                    min = Minimum(p2, p3, dimension);
                }
                min = Minimum(p1, min, dimension);
            }
            return min;
        }

        private HilbertTree()
        {
            //create via factory method
        }

        /// <summary>
        /// Factory method to create a hilbert tree from a list of data objects.
        /// </summary>
        /// <param name="data"></param>
        /// <returns></returns>
        public static HilbertTree BuildTree(IList<IHilbertTreeNode> data)
        {
            HilbertTree tree = new HilbertTree();
            if (data == null || data.Count == 0)
            {
                tree._rootNode = null;
            }
            else
            {
                tree._rootNode = new Node(data[0], Node.LowAndHighCombination.LowXLowY);
                tree._rootNode.ControlledRegion = new ComputationalRectangle(int.MinValue, int.MinValue, int.MaxValue, int.MaxValue);
                tree._rootNode.Insert(new Node(data[0], Node.LowAndHighCombination.LowXHighY));
                tree._rootNode.Insert(new Node(data[0], Node.LowAndHighCombination.HighXLowY));
                tree._rootNode.Insert(new Node(data[0], Node.LowAndHighCombination.HighXHighY));

                for (int i = 1; i < data.Count; i++)
                {
                    tree._rootNode.Insert(new Node(data[i], Node.LowAndHighCombination.LowXLowY));
                    tree._rootNode.Insert(new Node(data[i], Node.LowAndHighCombination.LowXHighY));
                    tree._rootNode.Insert(new Node(data[i], Node.LowAndHighCombination.HighXLowY));
                    tree._rootNode.Insert(new Node(data[i], Node.LowAndHighCombination.HighXHighY));
                }
            }
            return tree;
        }

        /// <summary>
        /// create a new node representing a certain map object
        /// </summary>
        /// <param name="data">the tree node data, for which the new nodes to create</param>
        public void InsertNode(IHilbertTreeNode data)
        {
            if (_rootNode == null)
            {
                _rootNode = new Node(data, Node.LowAndHighCombination.LowXLowY);
                _rootNode.ControlledRegion = new ComputationalRectangle(int.MinValue, int.MinValue, int.MaxValue, int.MaxValue);
            }
            else
            {
                _rootNode.Insert(new Node(data, Node.LowAndHighCombination.LowXLowY));
            }
            _rootNode.Insert(new Node(data, Node.LowAndHighCombination.LowXHighY));
            _rootNode.Insert(new Node(data, Node.LowAndHighCombination.HighXLowY));
            _rootNode.Insert(new Node(data, Node.LowAndHighCombination.HighXHighY));
        }

        /// <summary>
        /// remove the node representing a map object
        /// </summary>
        /// <param name="data">the tree node data, for which all node have to be deleted</param>
        /// <returns></returns>
        public bool RemoveNode(IHilbertTreeNode data)
        {
            //version 1: directly delete objects
            _rootNode = Delete(data, _rootNode, 0, false, Node.LowAndHighCombination.LowXLowY);
            _rootNode = Delete(data, _rootNode, 0, false, Node.LowAndHighCombination.LowXHighY);
            _rootNode = Delete(data, _rootNode, 0, false, Node.LowAndHighCombination.HighXLowY);
            _rootNode = Delete(data, _rootNode, 0, false, Node.LowAndHighCombination.HighXHighY);
            //version 2: mark deleted objects and remove later in a rebalancing step
            //int retcode = root.Remove(mo);
            /*if (retcode == KDNode.KDNODE_REMOVE_RIGHTWASNULL)
            {
                root = root.left;
            }
            else if (retcode == KDNode.KDNODE_REMOVE_LEFTWASNULL)
            {
                root = root.right;
            }
            else if (retcode == KDNode.KDNODE_REMOVE_WHOLETREE)
            {
                root = null;
            }
            else if (retcode == KDNode.KDNODE_REMOVE_TRAVERSE)
            {
                root.markDeleted = true;
            }*/
            return false;
        }

        /// <summary>
        /// remove all nodes, this will release all references inside the tree and between nodes.
        /// </summary>
        public void RemoveAll()
        {
            if (_rootNode != null)
            {
                _rootNode.Destroy();
            }
            _rootNode = null;
        }

        public static void RangeSearch(Node v, ComputationalShape range, HashSet<IHilbertTreeNode> ret)
        {
            if (v == null || range == null) return;
            if (v.IsLeaf())
            {
                if (v.StoredData.Contains(range) != ShapeOverlapping.Outside && !ret.Contains(v.StoredData))
                {
                    ret.Add(v.StoredData);
                }
                return;
            }
            ShapeOverlapping contains;
            if ((contains = range.Contains(v.ControlledRegion)) == ShapeOverlapping.Contains)
            {
                v.Report(ref ret);
            }
            else if (contains == ShapeOverlapping.Intersects ||
                range.Contains(v.BoundingRegion) != ShapeOverlapping.Outside)
            {
                //if node intersects or the bounds of contained objects overlap query
                RangeSearch(v.Left, range, ret);
                RangeSearch(v.Right, range, ret);
                if (v.StoredData.Contains(range) != ShapeOverlapping.Outside && !ret.Contains(v.StoredData))
                {
                    ret.Add(v.StoredData);
                }
            }
        }


        /// <summary>
        /// sort the distance of nodes, for k-nearest search
        /// alternatively use quicksort
        /// </summary>
        /// <param name="dists"></param>
        /// <param name="start"></param>
        /// <param name="length"></param>
        /// <param name="indices"></param>
        private void MergeSortDistances(double[] dists, int start, int length, int[] indices)
        {
            if (length <= 1) return;
            int l05 = length / 2;
            MergeSortDistances(dists, start, l05, indices);
            MergeSortDistances(dists, start + l05, length - l05, indices);
            MergeDistances(dists, start, start + l05, start + length, indices);
        }

        /// <summary>
        /// merge step of merge sort for ordering tree data according to their distance to a point
        /// for k-nearest search
        /// </summary>
        /// <param name="dists"></param>
        /// <param name="start"></param>
        /// <param name="middle"></param>
        /// <param name="end"></param>
        /// <param name="indices"></param>
        private void MergeDistances(double[] dists, int start, int middle, int end, int[] indices)
        {
            int ileft = start;
            int iright = middle;
            int icount = 0;
            int[] tind = null;
            if (end - start > 0)
            {
                tind = new int[end - start];
            }
            if (tind == null) return;
            while (ileft < middle && iright < end)
            {
                if (dists[indices[ileft]] <= dists[indices[iright]])
                {
                    tind[icount++] = indices[ileft++];
                }
                else
                {
                    tind[icount++] = indices[iright++];
                }
            }
            while (ileft < middle)
            {
                tind[icount++] = indices[ileft++];
            }
            while (iright < end)
            {
                tind[icount++] = indices[iright++];
            }
            for (int i = 0; i < tind.Length; i++)
            {
                indices[i + start] = tind[i];
            }
        }

        /// <summary>
        /// return the k-kearest data objects in a range around a certain point
        /// maybe extended by restricting to a map object type
        /// <remarks>Does not support priority search</remarks>
        /// </summary>
        /// <param name="k">number of objects to retrieve</param>
        /// <param name="pt">point</param>
        /// <param name="types">0-all, 1-nodes, 2-edges</param>
        /// <param name="range">range around the point</param>
        /// <returns>list of at most k data objects</returns>
        public List<IHilbertTreeNode> FindkNearest(int k, System.Windows.Point pt, int types, double range)
        {
            if (k < 1) return null;
            HashSet<IHilbertTreeNode> ret = new HashSet<IHilbertTreeNode>();
            ComputationalShape circle = new ComputationalCircle(pt.X, pt.Y, range);
            if (_rootNode != null) RangeSearch(_rootNode, circle, ret);
            if (ret.Count == 0) return null;
            List<IHilbertTreeNode> retList = new List<IHilbertTreeNode>(ret);
            ret = null;
            if (types != 0)
            {
                for (int i = retList.Count - 1; i > -1; i--)
                {
                    bool keep = false;
                    int type_i = retList[i].Category;
                    if ((type_i & types) == type_i)
                    {
                        //check if classes are equal or ttype_i inherits from requested type
                        keep = true;
                    }
                    if (!keep)
                    {
                        retList.RemoveAt(i);
                    }
                }
            }
            if (ret.Count < k)
            {
                //the number of potential results is smaller than the requested number
                //return all results
                return retList;
            }
            //otherwise get the nearest k results
            double[] dd = new double[ret.Count];
            int[] indices = new int[dd.Length];
            for (int i = 0; i < dd.Length; i++)
            {
                dd[i] = retList[i].GetBoundingBox().GetDistanceFrom(pt);
                indices[i] = i;
            }
            MergeSortDistances(dd, 0, dd.Length, indices);
            List<IHilbertTreeNode> ret2 = new List<IHilbertTreeNode>();
            for (int i = 0; i < k; i++)
            {
                ret2.Add(retList[indices[i]]);
            }
            return ret2;
        }

        /// <summary>
        /// find the nearest map object to a given point in a range
        /// </summary>
        /// <param name="xx">x coordinate of the point</param>
        /// <param name="yy">y coordinate of the point</param>
        /// <param name="range">range around the point</param>
        /// <param name="direction">0=all, 1=north, 2=east, 4=south, 8=west, 16=not north, 32=not east, 64=not south, 128=not west</param>
        /// <param name="types">0-all;</param>
        /// <returns>the nearest map object or null</returns>
        public IHilbertTreeNode FindNearest(double xx, double yy, double range, int direction, int types)
        {
            if (_rootNode == null) return null;
            IHilbertTreeNode data = _rootNode.FindNearest(xx, yy, range, direction, types);
            if (data == null || (types != 0 && (data.Category & types) != data.Category))
            {
                return null;
            }
            return data;
        }

        /// <summary>
        /// Generate a random order of a given number of objects.
        /// </summary>
        /// <param name="numberOfObjects"></param>
        /// <returns>The randomly sorted indices</returns>
        public static int[] CreateRandomOrder(int numberOfObjects)
        {
            if (numberOfObjects < 0)
            {
                throw new ArgumentOutOfRangeException("numberOfObjects must be greater or equal 0");
            }
            int[] ret = new int[numberOfObjects];
            for (int i = 0; i < numberOfObjects; i++)
            {
                ret[i] = i;
            }
            Random rng = new Random();
            for (int n = numberOfObjects; n > 1; n--)
            {
                int k = rng.Next(n);
                int tmp = ret[k];
                ret[k] = ret[n - 1];
                ret[n - 1] = tmp;
            }
            return ret;
        }
    }

    /// <summary>
    /// internal use for k-nearest
    /// </summary>
    internal class DistanceNode
    {
        internal double Distance;
        internal Node Node;
    }
}
